package com.yq.leetcodeOld;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName Solution76
 * @Description TODO
 * @Author yaoqiang
 * @Date 2022/3/16 10:39
 * @Version 1.0
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 注意：
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 * 示例 1：
 * <p>
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 示例 2：
 * 输入：s = "a", t = "a"
 * 输出："a"
 * <p>
 * 示例 3:
 * 输入: s = "a", t = "aa"
 * 输出: ""
 * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
 * 因此没有符合条件的子字符串，返回空字符串。
 * "ADOBECODEBANC"
 * "ABC"
 * <p>
 * 滑动窗口模板:
 * <p>
 * <p>
 * Map<Character, Integer> window = new HashMap<>();
 * Map<Character, Integer> need = new HashMap<>();
 * //需要的字符传入need
 * for (char c : t.toCharArray()) {
 * need.put(c, need.getOrDefault(c, 0) + 1);
 * }
 * int left = 0;
 * int right = 0;
 * while (right < s.length()) {
 * //c是移入窗口的字符
 * char c = s.charAt(right);
 * //右边界右移
 * right++;
 * <p>
 * //进入窗口的一系列操作.....
 * <p>
 * //当满足时,需要进行窗口缩减
 * while (win收缩) {
 * char d = s.charAt(left);
 * //左边界右移
 * left++;
 * <p>
 * //出窗口的一系列操作.....
 * }
 * }
 * 此模板可以解决
 * 438. 找到字符串中所有字母异位词
 * 3. 无重复字符的最长子串
 * 567. 字符串的排列
 * <p>
 * 此题详情请看代码注释:
 * <p>
 * <p>
 * public String minWindow(String s, String t) {
 * if (s.length() < t.length()) {
 * return "";
 * }
 * //创建两个双列集合 key为字符 value为次数
 * //一个来装我们窗口中当前符合要求的字符
 * //一个用来装我们需要的字符数量,
 * Map<Character, Integer> window = new HashMap<>();
 * Map<Character, Integer> need = new HashMap<>();
 * //需要的字符传入need
 * for (char c : t.toCharArray()) {
 * need.put(c, need.getOrDefault(c, 0) + 1);
 * }
 * //创建双指针来标志滑动窗口
 * int left = 0;
 * int right = 0;
 * //valid变量表示窗口中满足need条件的字符个数
 * //如果vaild==need.size 说明窗口已经满足条件了
 * int valid = 0;
 * //记录最小覆盖子串的起始索引及长度
 * int start = 0;
 * int len = Integer.MAX_VALUE;
 * while (right < s.length()) {
 * //c是移入窗口的字符
 * char c = s.charAt(right);
 * //右边界右移
 * right++;
 * //判断该值是否需要进入窗口
 * if (need.containsKey(c)) {
 * window.put(c, window.getOrDefault(c, 0) + 1);
 * //判断是否需要跟新valid
 * // !!!不能用== 由于Integer的长度限制 有一个测试用例会通不过
 * if (window.get(c).equals(need.get(c))) {
 * valid++;
 * }
 * }
 * //当满足时,需要进行窗口缩减
 * while (valid == need.size()) {
 * //记录最短覆盖串
 * if (right - left < len) {
 * start = left;
 * len = right - left;
 * }
 * //得到出窗口的字符
 * char d = s.charAt(left);
 * //左边界右移
 * left++;
 * //判断该字符是否在我们的窗口中
 * if (need.containsKey(d)) {
 * //如果出去的字符是我们需要的则valid需要更新
 * if (window.get(d).equals(need.get(d))) {
 * valid--;
 * }
 * //d出窗口
 * window.put(d, window.get(d) - 1);
 * }
 * }
 * }
 * return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
 * }
 */
public class Solution76 {
    public static void main(String[] args) {
        String res = minWindow2("ADOBECODEBANC", "ABC");
        String result=minWindow("ADOBECODEBANC", "ABC");
        System.out.println(res);
    }
    public static String minWindow(String s,String t){
        if(s.length()<t.length()||s.length()==0|| t.length()==0)return ""; //排除空的异常
        //创建两个hashmap一个存窗口中关键字出现的次数，一个need存放需要的字符出现的次数
        HashMap<Character,Integer> window=new HashMap<>();
        HashMap<Character, Integer> need=new HashMap<>();
        //将t放入到need中，将s遍历的时候再放入窗口的字符和出现次数
        for (char c:t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);  //string.toCharArray()  hashmap.getOrDefalut(c,0)
        int left=0,right=0; //左右窗户
        int valid=0; //表示窗户中满足need的条件个数，如果valid==need.size说明窗口满足条件了
        int start=0;
        int len=Integer.MAX_VALUE;
        while (right<s.length()){
            char c = s.charAt(right); //c是进度，类似for循环的i，此刻就是右窗
            right++;//每次村换right都是++
            //判断当前值是否要进入窗口
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                //判断是否要更新valid， 用equals替代==，不然由于integer的长度限制，有一个测试用例会不会通过
                if(window.get(c).equals(need.get(c))){valid++;} //比如A，在窗口中出现的次数和需要的次数相同，valid++
            }
            //当满足条件，进行窗户收缩，用来优化窗口
            while (valid==need.size()){
                //记录最短的
                if(right-left<len){
                    start=left;
                    len=right-left;
                }
                char d=s.charAt(left); //得到出窗口的字符
                left++;//左边界右移
                //判断左边出窗口的是否在我们的窗口，如果在需要更新valid
                if(need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){valid--;}
                    window.put(d,window.get(d)-1);
                }
            }
        }

        return len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    }



    public static String minWindow2(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        //创建两个双列集合 key为字符 value为次数
        //一个来装我们窗口中当前符合要求的字符
        //一个用来装我们需要的字符数量,
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        //需要的字符传入need
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        //创建双指针来标志滑动窗口
        int left = 0;
        int right = 0;
        //valid变量表示窗口中满足need条件的字符个数
        //如果vaild==need.size 说明窗口已经满足条件了
        int valid = 0;
        //记录最小覆盖子串的起始索引及长度
        int start = 0;
        int len = Integer.MAX_VALUE;
        while (right < s.length()) {
            //c是移入窗口的字符
            char c = s.charAt(right);
            //右边界右移
            right++;
            //判断该值是否需要进入窗口
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                //判断是否需要跟新valid
                // !!!不能用== 由于Integer的长度限制 有一个测试用例会通不过
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            //当满足时,需要进行窗口缩减
            while (valid == need.size()) {
                //记录最短覆盖串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                //得到出窗口的字符
                char d = s.charAt(left);
                //左边界右移
                left++;
                //判断该字符是否在我们的窗口中
                if (need.containsKey(d)) {
                    //如果出去的字符是我们需要的则valid需要更新
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    //d出窗口
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);

    }

}
